package leetcode;

import java.util.ArrayDeque;
import java.util.Arrays;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-26 12:48
 **/
public class LeetCode5966 {

    public int[] recoverArray(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1, result[] = new int[nums.length / 2];; i++) {
            if (nums[i] > nums[0] && (nums[i] - nums[0]) % 2 == 0) {
                ArrayDeque<Integer> deque = new ArrayDeque<>();
                for (int j = 0, k = 0; j < nums.length; j++) {
                    if (!deque.isEmpty() && deque.peek() == nums[j]) {
                        deque.poll();
                    } else if (k == result.length) {
                        break;
                    } else {
                        deque.offer(nums[j] + nums[i] - nums[0]);
                        result[k++] = nums[j] + (nums[i] - nums[0]) / 2;
                    }
                }
                if (deque.isEmpty()) {
                    return result;
                }
            }
        }
    }

}
